
/*
Description:
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

//https://leetcode.com/problems/single-number-ii/discuss/43296/An-General-Way-to-Handle-All-this-sort-of-questions.
//https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	//Q : Most elements appeared k times, except one.Find this "one".
	int singleNumber(vector<int>& s)
	{
		vector<int> t(32);////Made a array contain 32 elements.
		int sz = s.size();
		int i, j, n;
		for (i = 0; i < sz; ++i)
		{
			n = s[i];
			for (j = 31; j >= 0; --j)
			{
				t[j] += n & 1;//Find the last digit.
				n >>= 1;
				if (!n)
					break;
			}
		}
		int res = 0;
		for (j = 31; j >= 0; --j)
		{
			n = t[j] % 3;//"3" represents k times. 
			if (n)
				res += 1 << (31 - j);
		}
		return res;
	}

	/*
	Bitwise operators. Where arithmetic operators treat values as numbers, bitwise operators treat values as strings of bits.
	"~" is NOT, which takes a single value as a parameter and returns a value that has each bit in the opposite state as the corresponding bit in the parameter.
	"&" is AND, which takes two parameters and returns a value where each bit is on iff the corresponding bit is on in both parameters.
	"^" is XOR, which takes two parameters and returns a value where each bit is on iff the corresponding bit is on in exactly one of the parameters.
	*/
	int singleNumber2(vector<int> & nums) {
		int ones = 0, twos = 0;
		for (int i = 0; i < nums.size(); i++) {
			ones = (ones ^ nums[i]) & ~twos;
			twos = (twos ^ nums[i]) & ~ones;
		}
		return ones;
	}
	
	int singleNumber1(vector<int>& nums) {
		int oc = 0, tc = 0, f = 0, z;
		for (int x : nums) {
			tc |= (z = tc & x) ^ z ^ (x &= ~z) ^ x ^ (tc &= ~z) ^ tc ^ ((~oc^x)&x) ^ (oc ^= x) ^ oc;
		}
		return oc;
	}

	int singleNumber0(vector<int>& nums) {
		int len = nums.size();
		int group = len / 2;
		for (int i = 0; i < group; i++)
		{
			
		}

	}
	
};

int _singleNumber2()
{
	vector<int> nums{ 2,2,3,2 };
	
	Solution solu;
	int num;

	num = solu.singleNumber(nums);

	cout << "nums: " << endl;
	for (auto n : nums) cout << n << " ";
	cout << endl;
	cout << "num: " << num << endl;
	return 0;
}